package org.example.myleet.treeset;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.Parser;

import java.util.*;

public class TreeSetSolution {

    //p855
    static class ExamRoom {

        private int cnt;
        private int n;
        private TreeSet<Integer> seated;

        public ExamRoom(int n) {
            cnt = 0;
            this.n = n;
            seated = new TreeSet<>(Comparator.naturalOrder());
        }

        public int seat() {
            int seat;
            if (cnt == 0) {
                //没有的时候坐0
                seated.add(0);
                seat = 0;
            } else if (cnt == 1) {
                //已经坐了1个人，看看是最左边还是最右边好
                int s = seated.first();
                if (s == 0) {
                    seated.add(n - 1);
                    seat = n - 1;
                } else if (s == n - 1) {
                    seated.add(0);
                    seat = 0;
                } else {
                    int dist = s / 2;
                    if ((n - s) / 2 > dist) {
                        seated.add(n - 1);
                        seat = n - 1;
                    } else {
                        seated.add(0);
                        seat = 0;
                    }
                }
            } else {
                //已经坐了超过1个人，则遍历每个相邻位置，取距离最大的间隔然后坐中间
                int candidate = 0;
                int dist = Integer.MIN_VALUE;
                if (seated.size() > 0) {
                    Iterator<Integer> iterator = seated.iterator();
                    int left = iterator.next();
                    if (left > 0) {
                        dist = (left + 1) / 2;
                        candidate = 0;
                    }
                    while (iterator.hasNext()) {
                        int right = iterator.next();
                        int d = (right - left) / 2;
                        if (d > dist) {
                            dist = d;
                            candidate = left + dist;
                        }
                        left = right;
                    }
                    if (left < n - 1) {
                        int d = (n - left) / 2;
                        if (d > dist) {
                            dist = d;
                            candidate = left + dist;
                        }
                    }
                }
                seat = candidate;
            }
            //学生坐下，加入到有序集合中，自动排序
            seated.add(seat);
            ++cnt;
            return seat;
        }

        public void leave(int p) {
            seated.remove(p);
            --cnt;
        }
    }

    //p874
    public int robotSim(int[] commands, int[][] obstacles) {
        Map<Integer, TreeSet<Integer>> obstacleXMapY = new HashMap<>();
        Map<Integer, TreeSet<Integer>> obstacleYMapX = new HashMap<>();
        for (int[] obstacle : obstacles) {
            TreeSet<Integer> treeSet = obstacleXMapY.getOrDefault(obstacle[0], new TreeSet<>());
            treeSet.add(obstacle[1]);
            obstacleXMapY.put(obstacle[0], treeSet);
            treeSet = obstacleYMapX.getOrDefault(obstacle[1], new TreeSet<>());
            treeSet.add(obstacle[0]);
            obstacleYMapX.put(obstacle[1], treeSet);
        }
        int direction = 0;
        int x = 0, y = 0;
        int maxEulaDistance = 0;
        for (int command : commands) {
            if (command < 0) {
                if (command == -2) {
                    direction--;
                } else if (command == -1) {
                    direction++;
                }
                direction = (direction + 4) % 4;
            } else {
                switch (direction) {
                    case 0: {
                        TreeSet<Integer> treeSet = obstacleXMapY.get(x);
                        if (treeSet != null) {
                            Integer ceiling = treeSet.ceiling(y + 1);
                            if (null != ceiling && y + command >= ceiling) {
                                y = ceiling - 1;
                            } else {
                                y += command;
                            }
                        } else {
                            y += command;
                        }
                        break;
                    }
                    case 1: {
                        TreeSet<Integer> treeSet = obstacleYMapX.get(y);
                        if (treeSet != null) {
                            Integer ceiling = treeSet.ceiling(x + 1);
                            if (null != ceiling && x + command >= ceiling) {
                                x = ceiling - 1;
                            } else {
                                x += command;
                            }
                        } else {
                            x += command;
                        }
                        break;
                    }
                    case 2: {
                        TreeSet<Integer> treeSet = obstacleXMapY.get(x);
                        if (treeSet != null) {
                            Integer floor = treeSet.floor(y - 1);
                            if (null != floor && y - command <= floor) {
                                y = floor + 1;
                            } else {
                                y -= command;
                            }
                        } else {
                            y -= command;
                        }
                        break;
                    }
                    case 3: {
                        TreeSet<Integer> treeSet = obstacleYMapX.get(y);
                        if (treeSet != null) {
                            Integer floor = treeSet.floor(x - 1);
                            if (null != floor && x - command <= floor) {
                                x = floor + 1;
                            } else {
                                x -= command;
                            }
                        } else {
                            x -= command;
                        }
                        break;
                    }
                    default: break;
                }
                maxEulaDistance = Math.max(maxEulaDistance, x * x + y * y);
            }
        }
        return maxEulaDistance;
    }

    /**
     * 2080【哈希树+二分查找】区间内查询数字的频率
     */
    static class RangeFreqQuery {
        private Map<Integer, TreeMap<Integer, Integer>> valueMapIds;
        private Map<Long, Integer> answerMap;
        public RangeFreqQuery(int[] arr) {
            valueMapIds = new HashMap<>();
            answerMap = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                int num = arr[i];
                TreeMap<Integer, Integer> ids = valueMapIds.getOrDefault(num, new TreeMap<>());
                ids.put(i, ids.size() + 1);
                valueMapIds.put(num, ids);
            }
        }
        public int query(int left, int right, int value) {
            long label = left * 100010001L + right * 10001L + value;
            Integer answer = answerMap.get(label);
            if (null != answer) return answer;
            TreeMap<Integer, Integer> ids = valueMapIds.get(value);
            if (null == ids) return 0;
            Map.Entry<Integer, Integer> leftEntry = ids.ceilingEntry(left);
            Map.Entry<Integer, Integer> rightEntry = ids.floorEntry(right);
            if (null == leftEntry || null == rightEntry) {
                answer = 0;
            } else {
                answer = rightEntry.getValue() - leftEntry.getValue() + 1;
            }
            answerMap.put(label, answer);
            return answer;
        }
    }

    /**
     * 2353【哈希树】设计食物评分系统
     */
    static class FoodRatings {
        private Map<String, Integer> foodRating;
        private Map<String, String> foodMapCuisine;
        private Map<String, TreeSet<String>> cuisineCollection;
        public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
            foodRating = new HashMap<>();
            foodMapCuisine = new HashMap<>();
            cuisineCollection = new HashMap<>();
            int n = foods.length;
            for (int i = 0; i < n; ++i) {
                String food = foods[i];
                String cuisine = cuisines[i];
                int rating = ratings[i];
                foodRating.put(food, rating);
                foodMapCuisine.put(food, cuisine);
                TreeSet<String> collection = cuisineCollection.get(cuisine);
                if (null == collection) {
                    collection = new TreeSet<>((foodA, foodB) -> {
                        if (foodA.equals(foodB)) return 0;
                        int fra = foodRating.get(foodA), frb = foodRating.get(foodB);
                        if (fra == frb) return foodA.compareTo(foodB);
                        return fra < frb ? 1 : -1;
                    });
                }
                collection.add(food);
                cuisineCollection.put(cuisine, collection);
            }
        }

        public void changeRating(String food, int newRating) {
            TreeSet<String> collection = cuisineCollection.get(foodMapCuisine.get(food));
            collection.remove(food);
            foodRating.put(food, newRating);
            collection.add(food);
        }

        public String highestRated(String cuisine) {
            TreeSet<String> collection = cuisineCollection.get(cuisine);
            return collection.first();
        }
    }

    /**
     * 2502【哈希树】设计内存分配器
     */
    static class Allocator {
        private int n;
        private Map<Integer, List<int[]>> allocated; //mId : [i, len]
        private TreeMap<Integer, Integer> freeRanges; //i : len
        public Allocator(int n) {
            this.n = n;
            allocated = new HashMap<>();
            freeRanges = new TreeMap<>();
            freeRanges.put(0, n);
        }

        public int allocate(int size, int mID) {
            for (Integer i : freeRanges.navigableKeySet()) {
                Integer len = freeRanges.get(i);
                if (len >= size) {
                    List<int[]> allocations = allocated.getOrDefault(mID, new ArrayList<>());
                    allocations.add(new int[]{i, size});
                    allocated.put(mID, allocations);
                    freeRanges.remove(i);
                    int remain = len - size;
                    if (remain > 0) {
                        freeRanges.put(i + size, remain);
                    }
                    return i;
                }
            }
            return -1;
        }

        public int freeMemory(int mID) {
            List<int[]> allocations = allocated.remove(mID);
            if (null == allocations || allocations.isEmpty()) {
                return 0;
            }
            int freeCnt = 0;
            for (int[] allocation : allocations) {
                freeCnt += allocation[1];
                freeRanges.put(allocation[0], allocation[1]);
            }
            Integer prev = null, prevLen = null;
            List<Integer> removeIndexes = new ArrayList<>();
            for (Integer i : freeRanges.navigableKeySet()) {
                if (null == prev) {
                    prev = i;
                    prevLen = freeRanges.get(i);
                } else {
                    if (prev + prevLen == i) {
                        int len = freeRanges.get(i);
                        prevLen += len;
                        freeRanges.put(prev, prevLen);
                        removeIndexes.add(i);
                    } else {
                        prev = i;
                        prevLen = freeRanges.get(i);
                    }
                }
            }
            for (Integer i : removeIndexes) {
                freeRanges.remove(i);
            }
            return freeCnt;
        }
    }

    public static void main(String[] args) {
        FoodRatings foodRatings = new FoodRatings(new String[]{"czopaaeyl","lxoozsbh","kbaxapl"}, new String[]{"dmnuqeatj","dmnuqeatj","dmnuqeatj"}, new int[]{11,2,15});
        foodRatings.changeRating("czopaaeyl", 12);
        Assert.isTrue("kbaxapl".equals(foodRatings.highestRated("dmnuqeatj")));
        foodRatings.changeRating("kbaxapl", 8);
        foodRatings.changeRating("lxoozsbh", 5);
        Assert.isTrue("czopaaeyl".equals(foodRatings.highestRated("dmnuqeatj")));

//        Allocator allocator = new Allocator(10);
//        Assert.isTrue(0 == allocator.allocate(1, 1));
//        Assert.isTrue(1 == allocator.allocate(1, 2));
//        Assert.isTrue(2 == allocator.allocate(1, 3));
//        Assert.isTrue(1 == allocator.freeMemory(2));
//        Assert.isTrue(3 == allocator.allocate(3, 4));
//        Assert.isTrue(1 == allocator.allocate(1, 1));
//        Assert.isTrue(6 == allocator.allocate(1, 1));
//        Assert.isTrue(3 == allocator.freeMemory(1));
//        Assert.isTrue(-1 == allocator.allocate(10, 2));
//        Assert.isTrue(0 == allocator.freeMemory(7));

//        ExamRoom r1 = new ExamRoom(10);
//        Assert.isTrue(0 == r1.seat());
//        Assert.isTrue(9 == r1.seat());
//        Assert.isTrue(4 == r1.seat());
//        Assert.isTrue(2 == r1.seat());
//        r1.leave(4);
//        Assert.isTrue(5 == r1.seat());
//
//        ExamRoom r2 = new ExamRoom(10);
//        Assert.isTrue(0 == r2.seat());
//        Assert.isTrue(9 == r2.seat());
//        Assert.isTrue(4 == r2.seat());
//        r2.leave(0);
//        r2.leave(4);
//        Assert.isTrue(0 == r2.seat());
//        Assert.isTrue(4 == r2.seat());
//        Assert.isTrue(2 == r2.seat());
//        Assert.isTrue(6 == r2.seat());
//        Assert.isTrue(1 == r2.seat());
//        Assert.isTrue(3 == r2.seat());
//        Assert.isTrue(5 == r2.seat());
//        Assert.isTrue(7 == r2.seat());
//        Assert.isTrue(8 == r2.seat());
//        r2.leave(0);
//        r2.leave(4);
//        Assert.isTrue(0 == r2.seat());
//        Assert.isTrue(4 == r2.seat());
//        r2.leave(7);
//        Assert.isTrue(7 == r2.seat());
//        r2.leave(3);
//        Assert.isTrue(3 == r2.seat());
//        r2.leave(3);
//        Assert.isTrue(3 == r2.seat());
//        r2.leave(9);
//        Assert.isTrue(9 == r2.seat());

//        TreeSetSolution solution = new TreeSetSolution();
//        Assert.isTrue(100 == solution.robotSim(new int[]{-2,-1,-2,3,7}, Parser.parse("[[1,-3],[2,-3],[4,0],[-2,5],[-5,2],[0,0],[4,-4],[-2,-5],[-1,-2],[0,2]]")));
    }
}
